1. Field of the Invention
The present invention relates to hierarchical motion estimation of video data, and more particularly, to a method of hierarchical motion estimation, which allows motion estimation in various block modes.
2. Description of Related Art
Motion estimation, which is one technique for encoding video data, searches a previous frame for a macroblock that is the most similar to a macroblock in a current frame using a specified measurement function and thus obtains a motion vector indicating a difference between locations of the two macroblocks. Motion estimation is the most computationally expensive portion of video data encoding.
In motion estimation of a current block using a full search, if the current block is a 16×16 macroblock, the most similar macroblock to a macroblock in the current frame is searched within a previous frame and a motion vector indicating a difference between locations of the two macroblocks is obtained. A matching criterion value is calculated using a specified measurement function in motion estimation. A macroblock corresponding to the minimum matching criterion value in the previous frame serves as a previous macroblock corresponding to a current macroblock.
When performing motion estimation using the full search, a large amount of computation is required and the amount makes it difficult to implement real-time video data encoding.
To reduce the amount of computation required in motion estimation, various high-speed motion estimation techniques have been developed. A multi-resolution multiple candidate search (MRMCS) is one of them.
FIG. 1 is a conceptual view of a conventional MRMCS. Referring to FIG. 1, the conventional MRMCS includes a lower level 104, a middle level 102, and an upper level 100. At the lower level 104, a current block to be coded and a previous frame have their original resolutions, respectively. At the middle level 102, the original image of the lower level 104 is decimated horizontally and vertically at a 2-to-1 ratio in order to reduce the resolution. At the upper level 100, the image of the middle level 102 is again decimated horizontally and vertically at a 2-to-1 ratio in order to reduce the resolution. The conventional MRMCS hierarchically performs motion estimation using three images of different resolutions at each level, thereby making high-speed motion estimation possible.
The conventional MRMCS will be described in more detail. It is assumed that motion estimation is performed in units of a 16×16 macroblock and a search range of motion estimation is from −16 pixels to +16 pixels.
In a first operation, a block that is matched to a current 4×4 block that is reduced to ¼ of its original size is searched in a previous frame that is reduced to ¼ of its original size at the upper level 100. A search range is from −4 pixels to +4 pixels, which is ¼ of the original search range. A sum of absolute differences (SAD) is generally used as a criterion for block matching. As a result of block matching at the upper level 100, the best matched block of a current block and the second-best matched block of the current block are determined and a motion vector for each of the determined blocks is obtained.
In a second operation, at the middle level 102, based on three points including upper left apices of the two blocks determined at the upper level 100 and a point that is pointed by a motion vector obtained by taking a median value of motion vectors of three macroblocks that are already coded and located to the left side of, up from, and the upper right side of the current macroblock, a partial search that ranges from −2 pixels to +2 pixels is performed in a previous frame that is reduced to ½ of its original size, thereby obtaining the best matched block of the current block and a motion vector for that case.
In a third operation, based on a upper left apex of a block that is determined to be best matched to the current block at the middle level 102, a partial search that ranges from −2 pixels to +2 pixels is performed on a previous frame of the lower level 104, i.e., a previous frame having its original size, thereby finally obtaining the best matched macroblock of the current macroblock and a motion vector for that case.
Motion estimation adopted in video data encoding standards such as the recently developed H.264 standard (which is part of the Motion Picture Expert Group (MPEG) 4 standard) is performed on not only 16×16 blocks but sub-blocks of 16×8, 8×16, 8×8, 8×4, 4×8, and 4×4 in order to improve the accuracy of motion estimation and the efficiency of encoding.
FIGS. 2A-2D and 3A-3D show various block modes for motion estimation, which are used in H.264 standards. Referring to FIGS. 2A-2D, there is shown a 16×16 block mode, a 16×8 block mode, a 8×16 block mode, and a 8×8 block mode, respectively.
However, since the conventional MRMCS is designed to only perform motion estimation on a macroblock of 16×16 or 8×8, it cannot be used for blocks of various sizes as in H.264 standard.